package com.zp.self.module.level_4_算法练习.算法.动态规划;

/**
 * @author By ZengPeng
 * @Description 最初在一个记事本上只有一个字符 'A'。你每次可以对这个记事本进行两种操作：
 * Copy All (复制全部) : 你可以复制这个记事本中的所有字符(部分的复制是不允许的)。
 * Paste (粘贴) : 你可以粘贴你上一次复制的字符。
 * 给定一个数字 n 。你需要使用最少的操作次数，在记事本中打印出恰好 n 个 'A'。输出能够打印出 n 个 'A' 的最少操作次数。
 * @date in  2021/1/20 19:13
 * @Modified By
 * 参考：https://leetcode-cn.com/problems/2-keys-keyboard/solution/dong-tai-gui-hua-fa-javashi-xian-by-zyu/
 */
public class 力扣_650_只有两个键的键盘 {
    public static void main(String[] args) {

        System.out.println(minSteps(12));
    }

    //素数分解
    public static int minSteps(int n) {
        int[] dp = new int[n + 1];
        int h = (int) Math.sqrt(n);//只需要找到小于sqrt(n)的因子即可。内部循环只用到这里
        for (int i = 2; i <= n; i++) {
            dp[i] = i;
            for (int j = 2; j <= h ; j++) {
                if (i % j == 0) {//假设找到的因子是 j ，那么需要的最小步骤就是 dp[j] + dp[i/j]
                    dp[i] = dp[j] + dp[i / j];//dp[j]表示需要多少步生成这个因子，dp[i/j]表示需要多少步基于这个因子得到 i。
                    break;
                }
            }
        }
        return dp[n];
    }



    //动态规划
    public static int myAnswer(int n) {
        /*650. 只有两个键的键盘 ctrl+c ctrl+v*/
        //思路，满足最优子结构，无后效性，重复子结构，可考虑动态规划
        //阶段： n阶问题，每阶有j个子问题，既可以在已复制j个的基础上粘贴
        //状态： 粘贴之前必须复制（限定条件），复制有j个'A' 当前有‘i’个'A'
        //状态转移方程：dp[i][j]=min(dp[i-j][j]+1,dp[i][j]);
        //边界条件，每复制一次j个"A"要用一次操作，当i==j的时候可以全部复制
        if (n == 0)
            return 0;
        int[][] dp = new int[][]{};
        for (int i = 0; i <= n; i++) {
            dp[i][i] = n;//因为是求最小值，这里随便初始化一个值，但是要足够大，分析可知就算是每次只粘贴一个，那么最多操作数是n
        }
        dp[1][1] = 0;                //初始状态
        for (int i = 1; i <= n; i++) {
            int minNum = dp[i][1];    //纪录第二层循环的最小值 下面会用到
            for (int j = 1; j <= i; j++) {
                if (i - j >= 1) { //注意不要越界
                    dp[i][j] = Math.min(dp[i - j][j] + 1, dp[i][j]);    //i个A 要在i-j个A的基础上粘贴j个A
                    minNum = Math.min(minNum, dp[i][j]);
                }
                if (i == j)            //当i=j的时候 代表复制所有的"A" 肯定是在最小操作数的基础上复制，所以前面要纪录最小值
                    dp[i][j] = minNum + 1;
            }
        }
        return dp[n][n] - 1;
    }



}
